package 力扣日常刷题.木22二月.第20天226;

/**
 * @author 帅小伙
 * @date 2022/2/26
 * @description
 */
public class Demo158减绳子2 {


    public static void main(String[] args) {
        cuttingRope(100);
    }

    public static int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        final int MOD = 1000000007;
        int b = n%3;
        long rem = 1,x = 3;
        for (int a = n/3-1; a >0 ; a/=2) {
            if(a%2==1)rem =(rem *x)%MOD;
            x =  (x * x) %MOD;
        }
        if(b == 0) return (int)(rem * 3 %MOD);
        if(b == 1) return (int)(rem * 4 % MOD);
        return (int)(rem * 6 %MOD);
    }

}
